package myself.a015Dp;


/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class Knapsack {
    // 买菜策略，买或者不买

    // 暴力递归，递归写的越简单，答案越容易出
    // 简单就是递归参数中动态变化的最好 <= 2
    public static int maxValue(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        // 尝试函数！
        return process(w, v, 0, bag);
    }

    public static int process(int[] w, int[] v, int index, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
        // 不要当前商品
        int p1 = process(w, v, index + 1, rest);

        int p2 = 0;
        // 要当前商品
        int judge = process(w, v, index + 1, rest - w[index]);
        p2 = judge != -1 ? judge : p2;

        return Math.max(p1, p2);
    }

    // 跳过傻白甜，直接递归分析出 dp
    public static int dp(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }

        int N = w.length;

        int[][] cache = new int[bag + 1][N + 1];

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = cache[index + 1][rest];
                int p2 = 0;
                int judge = rest - w[index] < 0 ? -1 : cache[index + 1][rest - w[index]];
                p2 = judge != -1 ? v[index] + judge : p2;
                cache[index][rest] = Math.max(p1, p2);
            }
        }

        return cache[0][bag];
    }
}
